// 题目： 输出4000 0000以内的完全数
//      注：如果一个正整数除了它本身之外的其他因数之和等于它，则称之为完全数
// 一个例子：
//      6的真因子 1， 2， 3， 1+2+3 = 6， 所以6是完全数

#include <iostream>

/* @brief 判断一个数是否是完全数
 *
 * @param n: 待判断的数
 */
bool is_perfect_num(int n) {
  int sum = 1;  // 1 肯定是n的因子直接加上

  int i = 2;
  for (i = 2; i * i < n; i++)
    if ((n % i) == 0) {
      // 除了1和n，以及平方根，其他的因子肯定是成对出现，所以可以一次加两个因子，减少循环次数，加快速度
      sum += i;
      sum += n / i;
    }
  if (i * i == n)  // n 是平方数，则它的平方根因子只加一次
    sum += i;

  if (sum == n) return true;
  return false;
}

int main(int argc, char** argv) {
  int max_n = 40000000;
  for (int i = 6; i < max_n; i++) {
    if (is_perfect_num(i)) {
      std::cout << "found: " << i << std::endl;
    }
    if (i % 1000000 == 0) { // 每1000000个数打印一个标记
      std::cout << "================ " << i << std::endl;
    }
  }
    std::cout << "========== Finish search " << max_n << std::endl;
  return 0;
}

// 阅读：

// 前十个完全数是：int 范围内的只有5个！
//      6（1位）
//      28（2位）
//      496（3位）
//      8128（4位）
//      33550336（8位）
//      8589869056（10位）
//      137438691328（12位）
//      2305843008139952128（19位）
//      2658455991569831744654692615953842176（37位）
//      191561942608236107294793378084303638130997321548169216（54位）